package oct2013.linkednode;

public class PopulatingNextRightPointersinEachNodeII {
	public void connect(TreeLinkNode root) {
		if (root == null)
			return;
		TreeLinkNode head = root;
		TreeLinkNode tail = root;
		int level1 = 1, level2 = 0;
		while (head != null) {
			level1--;
			if (head.left != null) {
				level2++;
				tail.next = head.left;
				tail = tail.next;
			}
			if (head.right != null) {
				level2++;
				tail.next = head.right;
				tail = tail.next;
			}
			if (level1 == 0) {
				level1 = level2;
				level2 = 0;
				TreeLinkNode tmp = head;
				head = head.next;
				tmp.next = null;
			} else {
				head = head.next;
			}
		}
	}
}
